Greg Detre
14:30 Friday, September 27, 2002
are natural
languages context-free?
�John, Mary and Alice criticised himself, herself and herself respectively�
it�s the semantics that does the pairing, not the syntax
another argument for non-context-freeness of English:
�doctor, schmoctor� � duplication (they have to be identical) � can you apply that to an arbitrarily long string?
that�s not a fact about English, it�s just a language game (like pig latin), that�s part of language in general
what�s the difference between a word/language game and natural language
if you think there�s no difference, then the mother-schmother does show the non-context-freeness
but you could also question whether you could allow arbitrarily long �sch constructions
another argument for the non-CFness of NL
e.g. in German, you put all the verbs towards the end, except for the first verb (which comes second)
e.g. �John to the store going been have�
all the verbs go to the end in a subordinate clause
e.g. OR �John said, we Hans the house paint helped�
this is like the CF stack model
[Hans [the house paint] helped]
in Dutch (also Germanic), you do the same thing, except the verbs go in the opposite order
�� we Hans the house helped paint�
but now the dependencies cross, which looks non-CF
see Bresnen, Kaplan, Petersen et al. (late 1970s)
Gasdar & Pullam: this shows that the structure of Dutch may be strongly non-CF
but it doesn�t show that the strings are non-CF, because Dutch doesn�t have case-marking
need to find some natural language where the verb order is the same as Dutch but where the case shows up in objects
Chris thought that this was just a fluke, and just because we can�t find a particular actual natural language that is non-CF, we�ve found these two languages whose properties together would be non-CF
whereas I thought the opposite � properties aren�t independent, so if it has one but not the other or vice-versa (i.e. this stuff is really hard to find in the 6000 possible languages), that�s actually a pretty strong support that we aren�t designed to develop/speak non-CF languages (Chomskyan language instinct)
of course, there haven�t been many spontaneous eruptions of reading/writing and we are just about capable of learning that with the same spontaneity as spoken language�???
have there been any attempts to teach people artificial languages that aren�t CF to see if they can speak it?
there are some programming languages that are non-CF, but arguably we �speak� them differently
Swiss German (Shieber, 1986) is Dutch but with case-marking, as Bormbara(sp???)
Bormbara reduced it to ww (???)
they don�t seem to have really found any more
both these arguments were accepted by Gasdar & Pullam, which more or less ended the debate, because they were the most ornery � so we�ve concluded that natural languages aren�t CF
but they might be mildly CS
R <
CF <
mildly context-sensitive <
CS <
recursively-enumerable
no one has a reduction to anbncn? apparently not really
tree-adjoining graphs???
is NL even mildly-CS
re: constraints on free word-order languages
reduce it to permutations of anbncn under certain constraints
there are subsets of CF languages
e.g. deterministic vs non-determinstic
non-deterministic and deterministic FSMs are equivalent
but for pushdown automata, non-determinism makes it more powerful
p.s. Hockett�s table is a (weighted) transition matrix for a (probabilistic) FSM
language-automata equivalents:
regular languages:�������� FSMs
CFs:������������������������������������� pushdown automata
mildly CS:������������������������ embedded pushdown automata
CS:������������������������������� nonlinear �??? automata
RE:�������������������������������������� Turing machines
are NLs inherently ambiguous?
CF language is unambiguous if there�s an unambiguous grammar for it, i.e. they assign at most one derivation per string
if there doesn�t exist an unambiguous grammar for a given language �???
prepositional phrase ambiguity
e.g. �I saw the man in the park with a telescope�
it�s ambiguous in the informal sense
I saw him with the telescope
I saw the man in the park that has a telescope
I saw the man in the park who has a telescope
in the formal language sense, a grammar only has to accept the sentences that are in English and reject the ones that aren�t
so perhaps you could find an unambiguous grammar for English that only accepted strings that we would consider as being English sentences, but was only able to derive one of these (informally ambiguous) constructions
other examples of ambiguity:
Groucho Marx: �I shot an elephant in my pyjamas. How he got in my pyjamas I�ll never know� � playing on an ambiguity that�s (just shy of) apparent but �???
�I most enthusiastically recommend this candidate with no qualifications whatsoever�
let�s put the relationship between formal language theory and NL aside for now
it was linguists trying to formalise NL that started formal language theory
then CS took it over for building compilers
demos
Fernando Perreira & Shieber � TALK, very small program, for textbook
written in Prolog
example based on Frog and Toad (Arnold Lobel) � for children who�ve just learned to read
restricted vocab, but still a very difficult problem
assertions + questions
Perreira �Chat 80 NL Database� (1983)
medium-coverage NL program � interface for a geography database
AskJeeves
never got a reasonable result from AskJeeves
why do they have to vet every website they link to???
they cull the stuff that doesn�t get
asked
so paradoxically it answers well queries that it answers well
it�s good at high school homework and pop culture
Microsoft Office keyword
mainly just keyword search apparently, says Dave???
why would you want a NL interface?
queries are more concise (relative to certain formal languages) sometimes � hmmm
it�s fast/easy/convenient for us � requires no training
more similar to how you think � intuitive
when you can�t fully specify your question
it allows you to be vaguer � the right level of imprecision
voice
e.g. phone system
e.g. Telme (developed by Harvard graduates) doesn�t have any NLP
keyboards can be time-consuming/convenient
additional input (and indeed output) modality
non-alphabetic input
legacy � unstructured information
you hardly ever have a NL interface � it�s almost all direct manipulation
why not?
because even for small domains, it�s almost AI-complete, and it�s more irritating if it gets it wrong � broken expectations
they don�t work that well
a little bit of not working trumps any benefit
all the successful applications are low-level (e.g. voice recognition)
brittle
the error rate for Dragon is about 5% - phenomenal engineering achievement, but you would fire a person who got 1 in 20 words wrong
wordiness
btw: COBOL � apparently used English syntax
it had all the disadvantages of NL, i.e. it was wordy
but without the ability to infer missing steps
it was only so successful because the government mandated that you use it if contracted for them � which led to lots of COBOL programmers
thank god for the y2k bug which freed us from so much legacy code
expensive to build
HAL in 2001
a NL interface would alarm people
conversely, that�s raised expectations
uses the part of the brain for the speech rather than parallelising by using motor for keyboard/mouse
people can visually perceive info c.1000 times faster than they can speak, so you should just present you with all the information and let them select
eye-gaze selection?
but some things are much more complicated/hassle to express with direct manipulation
synthesising combinations/selections (quantification + definite description) are what NL is good at
how do the applications work?
the frog cookie assertion/question front-end for prolog was forming stored representions
i.e.
you need a lexicon to store words and their meaning, word forms, parts of speech etc., processed by parsing algorithm
parsing algorithm, to consider how the words go together and the resulting meanings
conceptual model
grounded in the environment, sensorimotor feedback
basic rules of inference/reasoning, common-sense
phonology, acoustics
primitives
different things in different situations, e.g. �I�, or �now�
or with different purposes/intended meanings, e.g. saying �it�s cold in here�, to try and make someone turn up the thermostat
= pragmatics
includes etiquette etc.???
though you can do away with this (because it�s a very hard problem) by seriously restricting the context
the NL pipeline: morphological � syntactic � semantic � pragmatic
Chomsky said that even if English was CF, it would be very tedious to try and capture all the different multiplicative rules that you�d need to capture English
e.g. nouns get modified by number, gender, a/an, mass/count etc.
when you do this with verbs, it�s called sub-categorisation (with respect to what kinds of objects they take)
Langendon(sp???)
� the vastness of NL
problem set on website under assignments
why don�t they make the new Star Trek Klingonesque language non-CF and see if people learn it easily at conventions???
how much sense does it make to talk of connectionist representations
to what extent is this stuf relevant to what our brains are actually doing???
well, we�re idealising from the behaviour people exhibit as a result of the brains in our heads
have to idealise that stuff away
e.g. we can�t manage arbitrary levels
so either you can say:
that this whole computational linguistic modelling is a waste of time
or you can say that brains make an approximation to this idealised language
but that�s jus ta processing limitation
this is the way that Shieber wants to go
what are the ways that you can restrict the domain??? how can you tell people so that they intuitively don�t go out of some grammatical bounds???
e.g. tell them it�s a children�s story. or tell them that it�s the sort of conversation you�d use on an airplane